home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / jpl_c.zip / SORTS.C < prev    next >
Text File  |  1986-05-18  |  2KB  |  45 lines
  1. /* 1.0  11-12-84 */
  2. /************************************************************************
  3.  *            Robert C. Tausworthe                *
  4.  *            Jet Propulsion Laboratory            *
  5.  *            Pasadena, CA 91009        1984        *
  6.  ************************************************************************
  7.  *    Shell sort subroutine, programmed using the algorithm in 
  8.  *
  9.  *    Kernighan, B. W., and Ritchie, D. M., THE C PROGRAMMING LANGUAGE,
  10.  *    Prentice-Hall Software Series, Englewood Cliffs, NJ, 1978,
  11.  *    pages 58 and  117.
  12.  *
  13.  *    It is written so the array type is unknown to the algorithm, but
  14.  *    known to comp() and exch().  The comparison function comp(i, j) 
  15.  *    must be positive if, and only if, the array elements at i and j 
  16.  *    are out of sort.  The function exch(i, j) must exchange array
  17.  *    elements indexed by i and j.
  18.  *
  19.  */
  20.  
  21. #include "defs.h"
  22. #include "stdtyp.h"
  23.  
  24. /************************************************************************/
  25.     VOID
  26. sortS(n, comp, exch)        /* Shell sort array of n items compared by
  27.                    comp(i, j), exchanged by exch(i, j).    */
  28. /*----------------------------------------------------------------------*/
  29. unsigned n;
  30. int (*comp)();
  31. VOID (*exch)();
  32. {
  33.     FAST unsigned i, k, gap;
  34.     FAST int j;
  35.  
  36.     for (gap = n / 2; gap > 0; gap /= 2)
  37.         for (i = gap; i < n; i++)
  38.         {    j = i - gap;
  39.             while (j >= 0 AND (*comp)(j, (k = j + gap)) > 0)
  40.             {    (*exch)(j, k);
  41.                 j -= gap;
  42.             }
  43.         }
  44. }
  45.